1. Technical Field
This invention relates to digital parallel processing systems, wherein a plurality of nodes communicate via messages sent over an interconnection network. In particular, this invention handles and keeps in chronological order the messages sent by each node when several sources are generating messages simultaneously.
2. Descriprion of the Prior Art
Known in the art is the use of network adapters for interfacing each node in a parallel system to a communication network. Such network adapters normally implement message buffers, usually a send First In First Out (FIFO) stack or buffer containing a plurality of messages to be sent to the network, and a receive (RCV) FIFO containing a plurality of messages which have been received from the network. The send FIFO stores and forwards messages to the network. The problem with this prior art scheme occurs when messages stored to the send FIFO can be generated from several sources, such as hardware controlled Direct Memory Access (DMA) operations and software controlled direct writes to the send FIFO using Programmed Input/Output (PIO) instructions to transfer data from processor registers directly into the FIFO. The problem is in regards to keeping the messages in order, as most parallel message passing systems require in-order message delivery, while maintaining DMA efficiency; that is, the purpose of DMA operations is to provide higher performance by enabling the processor and DMA channel to function simultaneously in an over-lapped manner. The two requirements of keeping message order and maintaining DMA efficiency are in direct conflict with each other. Typical solutions provide either message order or DMA efficiency, but not both. That is, efficient DMA message systems have been devised without message ordering, and message ordering systems have been implemented without supporting simultaneous overlapped DMA operations.
However, if solving the message ordering problem defeats the overlapped capability of DMA, it is not a solution at all--yet that is the typical approach. That is, the conventional way of keeping the messages in order is to defeat the overlap capability. This involves commanding one DMA operation at a time from the processor and requiring an interrupt when the DMA write to the send FIFO has completed. In response to the interrupt, processor software would then decide which message to write to the FIFO next--another DMA message or a PIO message. In this way, the software would directly control keeping the messages in order. However, because the processor must control the message ordering on a real time basis, this leads to a large loss of processing power. This additional processing slows the message handling and takes away much of the capabiltiy to do calculations in parallel with the DMA operations.
The concept of using a DMA controller to increase data transfer performance and to off-load the data transfer task from being performed under the direct control of a processor is known in the art. In one such solution, a DMA channel is implemented in hardware comprising channel registers for storing transfer parameters (address and byte count), registers for storing control parameters (status and command), a data assembler circuit for converting serial input/output (I/O) data to parallel memory data, and a channel control circuit that controls the registers and assembler. This approach requires continuous interaction between the processor and the DMA controller, such that one DMA operation at a time is commanded from the processor. When the DMA transfer is complete, the processor receives an interrupt to inform it that it can command another DMA operation. This type of interactive processing defeats much of the potential performance advantage gained by the use of the DMA controller.
Several improvements have been made on the basic DMA technique described above without really changing the most important one-at-a-time interactive approach. In one such improvement, processor and DMA access to memory are interleaved more efficiently using a processor unit containing a DMA controller having concurrent operation with the processor by dividing address and data into two parts.
In a major improvement, a DMA controller is operated to scatter or gather data into different areas of memory in a single operation. This is accomplished by using a buffer descriptor list (BDL) stored in a FIFO at the DMA controller, the BDL containing a plurality of buffer descriptor words (BDWs)--one for each part of the scatter/gather operation. The BDWs contain a memory address from where the data is to be accessed plus a byte count to define the length of the transfer. The local processor can preload the BDL with BDWs whenever the BDL has an available location, and these processor loads can be overlapped with the DMA operation. This approach works well for disk and tape units that deal with strictly DMA transfer-type operations. However, a more flexible approach is required for message transfer over an interconnection network in order to keep messages flowing at the highest possible performance over the network while providing for handling a mixture of message types, such as the DMA transfer of long messages intermixed with short messages sent directly from the processor without using the DMA function. Also, and of most importance, is the need to provide for mixing messages from different sources while at the same time maintaining the correct order of delivery of the messages. For message passing systems it is usually a requirement that messages be delivered in strict order or a system malfunction will occur.
In yet another improvement, the one-at-a-time interactive approach is avoided by using queue FIFOs which are similar to buffer descriptor lists (BDLs). In this technique, the DMA operation is partitioned into two queue FIFOS. First, a work FIFO contains a list DMAs to be done (same as BDLs). And second, a completion FIFO lists the BDWs for DMAs that have been completed. In this system, the processor can read the completion FIFO to determine which DMAs have completed. This is a twist on keeping track of which DMAs have completed. Another such twist provides a DMA priority contention scheme amongst multiple devices on the same bus.
Finally, in still another approach known in the art, both send and receive data FIFOs are implemented as part of an intelligent I/O processor for the purpose of DMA transferring data in either direction between global memory and the FIFOs.
However, none of the above solutions known in the art intermix DMA and processor and other generated messages while at the same time retaining message order and accommodating a mixture of message types essential for optimum performance in an interconnection network.
The present invention solves these problems by using a unique method and hardware apparatus at the network adapter. The solution both increases overlapped processing efficiency, while at the same time maintaining message order and relieving the software of this burden.